文章目录1 最优子结构性质2 子问题无关性质3 最优解递推关系4 子问题重叠性质5 零钱兑换问题 由《算法导论》，动态规划适用于解决具有以下性质的问题：最优子结构性质（其中包含子问题无关性质，也即无后效性），以及子问题重叠性质。 最优子结构性质 最优子结构性质有两个要求，其一为：问题的最优解可以由相关子问题的最优解组合而成。因为动态规划解决问题的方式是逐渐降低问题的规模，也就是将相对复杂的问题分解为若干子问题，再通过子问题的最优解组合去得到复杂问题的最优解，即我们必须能够组合，并且知道怎么组合（一般取决于实际问题）子问题最优解去得到最终的最优解。 一个经典的例子就是无权有向图的最短路径问题。假设要求出从A点到B点（A和B不是同一点）的最短路径，我们可以取出该最短路径 中的一中间点C，并断言路径中 和 这两部分，一定分别是从A点到C点的最短路径和从C点到B点的最短路径。即：从A到B的最短路径（复杂问题的最优解），由从A到C的最短路径（子问题的最优解）和从C到B的最短路径（子问题的最优解）组合得到，这就是最优子结构性质。 证明很简单，假设存在从A到C的一条更短的路径 ，我们可以用这条更短路径去替换 ，所得到的新的路径 ，其长度必定小于 ，而这与 最短矛盾。 在实际编程中，因为我们尚不知道最短路径，故也不知道C点是哪个点，所以我们是反过来，对每一个可能的中间结点C，都去求出对应的 和 ，然后取出它们长度之和最小的那一个，就是我们所要的那个点了。 子问题无关性质 最优子结构性质的另外一点，即子问题可以独立求解，或者说两个子问题是无关的。另一个说法是无后效性，即一个子问题的求解，不会影响后面子问题的求解。在上面的例子中，在最短路径 中，求最短路径 和 这两个过程一定是无关的，即求A到C的最短路径时，一定不影响求C到B的最短路径。这是因为，求 时，我们只关注C点以及之后将会遇到的点，至于我们怎么到达C点的，在求解时根本不会有任何作用。 严谨地说，我们可以断言， 和 中除了C点，不会再有其他公共的点。证明很简单，假设存在另一个公共点D，那么有 和 ，此时取路径 ，显然它比 更短，于是矛盾。这说明这两条最短路径其实并不共享任何点（除了C点，但C点无关紧要），所以它们的求解一定是无关的。 子问题无关性质，保证了当全局最优时，其所有子问题本身的解法，一定和我们求出的最优解一致。可以想象，如果子问题的求解是有关的，那么我们求出的子问题的最优解可能是互相矛盾的，取组合起来不一定是有效的解，更别说是不是全局最优解了。 最优解递推关系 在确保题目满足最优子结构性质后，接下来的一步就是确定最优解的递推关系，即子问题的最优解如何组合成全局最优解，该递推关系也称作状态转移方程。下面举一些例子： LeetCode 62. 不同路径 这个问题要求解的是矩阵中左上角到达右下角的不同路径总数，且只能往下走或往右走。这个问题满足最优子结构性质，假设以 表示从左上角 (1, 1) 到达 (x, y) 的路径数量，在非平凡的情况下（即不考虑边界）显然有： 这就是这个问题的状态转移方程。由递推式可知，如果我们从左往右，从上往下依次求出 dp，那么递推式中右边的总是已知的。但我们必须知道最开始的值是多少，才能从左往右从上往下不断地求，在这个问题里很简单，即： 也就是说，在求状态转移方程时，我们无需担心右边要怎么去求，而是总假定右边总是已知的，因为在递推式的作用下，右边的问题也会被继续分解，直到变为最简单的情况。 C#实现代码如下： public class … Continue reading 【算法】动态规划 Dynamic Programming